package com.cyy;

/**
 * 动态数组  可以自动扩容  扩容为 原来的 1.5倍
 * @author 会玩的洋洋
 * @since 2022-02-21
 * @param <E>
 */
public class DynamicArrayList<E> {
    /**
     * 动态数组元素
     */
    private E[] elements;
    /**
     * 动态数组中的现有值的大小
     */
    private int size;

    /**
     * 默认动态数组大小 = 10
     */
    private final static int DEFAULT_CAPACITY = 10;

    /**
     * 错误数据返回值
     */
    private final static int FAILED_RETURN = -1;

    public DynamicArrayList() {
        this(DEFAULT_CAPACITY);
    }

    public DynamicArrayList(int capacity) {
        // 如果传入的容量大小大于默认大小 则采用传入的大小 否则 使用默认大小
        this.elements = (E[])new Object[Math.max(capacity, DEFAULT_CAPACITY)];
        // size 初始化为 0
        this.size = 0;
    }

    /**
     * 清空所有元素
     */
    public void clear() {
        for (int i = 0; i < this.size; i++) {
            this.elements[i] = null;
        }
        this.size = 0;
    }

    /**
     * 元素数量
     */
    public int size() {
        return size;
    }

    /**
     * 判断是否空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 是否包含某个元素
     */
    public boolean contains(E element) {
        return this.indexOf(element) != FAILED_RETURN;
    }

    /**
     * 添加元素到尾部
     */
    public void add(E element) {
        add(this.size, element);
    }

    /**
     * 获取index位置的元素
     */
    public E get(int index) {
        rangeCheck(index);
        return elements[index];
    }

    /**
     * 设置index下标的元素
     * 返回覆盖的数
     */
    public E set(int index , E element) {
        rangeCheck(index);
        E oldElement = elements[index];
        elements[index] = element;
        return oldElement;
    }

    /**
     * 在index位置插入一个元素
     */
    public void add(int index , E element) {
        rangeCheckAdd(index);
        // size + 1 代表 新添加的容量大小
        ensureCapacity(this.size + 1);
        // 遍历，将 index 右部分向右移动
        for (int i = this.size; i > index; --i) {
            elements[i] = elements[i - 1];
        }
        elements[index] = element;
        ++size;
    }

    /**
     * 删除index位置的元素
     */
    public E remove(int index) {
        rangeCheck(index);
        E result = elements[index];
        // 遍历 将 index 右部分进行左移动  （优化了代码，以前是先从 index + 1 进行移动， 之后才进行删除 置空）
        for (int i = index; i < size; i++) {
            elements[i] = elements[i + 1];
        }
        --size;
        return result;
    }

    /**
     * 查看元素的索引
     */
    public int indexOf(E element) {
        // 如果元素为 null 直接用 == 比较
        if (element == null) {
            for (int i = 0; i < this.size; i++) {
                if (elements[i] == null) {
                    return i;
                }
            }
        } else {
            // 如果是元素 则用 equals 比较
            for (int i = 0; i < this.size; i++) {
                if (elements[i].equals(element)) {
                    return i;
                }
            }
        }
        return FAILED_RETURN;
    }

    /**
     * 判断输入的 index 是否符合正常范围
     * @param index 传入的 index 下标
     */
    private void rangeCheck(int index) {
        // index >= size 因为 如果 index == size 则越界异常
        if (index >= size || index < 0) {
            outOfBound(index);
        }
    }

    /**
     * 判断添加是 index 是否符合正常范围
     * @param index 传入的 index 下标
     */
    private void rangeCheckAdd(int index) {
        // index > size，添加可以 index == size
        if (index > size || index < 0) {
            outOfBound(index);
        }
    }

    private void outOfBound(int index) {
        throw new IndexOutOfBoundsException("越界异常：size = " + this.size + "index = " + index);
    }

    /**
     * 判断数组中是否超出容量
     * 扩容操作
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        // 没有超出容量大小
        if (capacity <= oldCapacity) {
            return;
        }

        // 如果超出容量大小  进行扩容 扩容为原来的 1.5 倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[])new Object[newCapacity];
        // 遍历进行深度 copy
        for (int i = 0; i < oldCapacity; i++) {
            newElements[i] = elements[i];
        }
        this.elements = newElements;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("DynamicArrayList{");
        for (int i = 0; i < this.size; i++) {
            sb.append(elements[i]).append(", ");
        }
        sb.append("size=").append(this.size).append("}");
        return sb.toString();
    }
}
